#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>

#define TYPE int

typedef struct Node
{
	TYPE data;
	struct Node* left;
	struct Node* right;
	struct Node* next;
}Node;



//创建结点
Node* creat_node(TYPE data)
{
	Node* node = malloc(sizeof(Node));
	node->data=data;
	node->left=NULL;
	node->right=NULL;
	node->next=NULL;
	return node;
}





//中序
void in_show(Node* root);
void _add_tree(Node** root,Node* node);
void add_tree(Node** root,TYPE data);
bool del_tree(Node** root,TYPE data);
void change(Node* root,Node** head);

bool son(Node* t1,Node* t2);





int main()
{
	Node* tree =NULL;// creat_node(50);
	Node* tree2=NULL;
	for(int i=0;i<10;i++)
	{
		TYPE data=rand()%100;
		add_tree(&tree,data);
		printf("%d\n\n",data);
	}

//		Node* tree2 =NULL;
		add_tree(&tree2,21);
		add_tree(&tree2,35);
		add_tree(&tree2,49);
		
//		printf("%d\n",data);

	printf("------------------------------\n");
	printf("\ntree1 中序：");
	in_show(tree);
	printf("\n");
	printf("\ntree2 中序：");
	in_show(tree2);
	printf("\n");

	son(tree,tree2);
	printf("==%s==\n",son(tree,tree2)?"yes":"no");


	Node* head =NULL;

 	 change(tree,&head);
	for(Node* node =head;NULL!=node;node=node->right)
	{
		printf("%d ",node->data);	
		
	}
	printf("\n");


//	del_tree(&tree,83);
//	in_show(tree);

}

//==========================判断子树==================================
bool _son(Node* t1,Node* t2)
{
	if(NULL == t2) return true;
	if(NULL == t1) return false;
	if(t1->data != t2->data) return false;
	return _son(t1->left,t2->left) && _son(t1->right,t2->right);
}
bool son(Node* t1,Node* t2)
{
	if(NULL == t2) return true;
	if(NULL == t1) return false;
	bool flag,flag1,flag2;
	if(t1->data ==t2->data)
	{
		flag = _son(t1,t2);	
	}
	flag1 = son(t1->left,t2);
	flag2 = son(t1->right,t2);
	return flag||flag1 ||flag2;
}
//=====================================================================



//======================转化为双向链表==============
void add_list(Node** head,Node* node )
{
	static Node* tail = NULL;
	if(NULL ==*head)
	{
		node->left = NULL;
		*head = node;	
		tail =node;
		return;
	}	
	tail->right = node;
	node->left = tail;
	tail = node;
}
void change(Node* root,Node** head)
{
	if(root ==NULL) return;
	change(root->left,head);
	add_list(head,root);
	change(root->right,head);
}
//===================================================








//中序
void in_show(Node* root)
{
	if(NULL == root) return;
	in_show(root->left);
	printf("%d ",root->data);
	in_show(root->right);
}




//修改后的添加===================
void _add_tree(Node** root,Node* node)
{
	if(NULL == *root) *root = node;

	else if((*root)->data > node->data)
		_add_tree(&(*root)->left,node);
	else
		_add_tree(&(*root)->right,node);
}

void add_tree(Node** root,TYPE data)
{
	_add_tree(root,creat_node(data));
}

//===============================

//删除
bool del_tree(Node** root,TYPE data)
{
	if((*root)->data ==data)
	{
		Node* node =* root;
		*root = node->left;
		_add_tree(root,node->right);
		free(node);			
		return true;	
	}
	else if((*root)->data >data)
		return del_tree(&(*root)->left,data);
	else 
		return del_tree(&(*root)->right,data);
}


